package com.agile.leetcode.difficult;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 *
 *
 *
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 *
 *
 *
 *
 *
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 *
 *
 *
 * 示例:
 *
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 * @Author:ChenZhangKun
 * @Date: 2021/4/14 12:01
 */
public class LargestRectangleArea {
    public static void main(String[] args) {
        LargestRectangleArea area = new LargestRectangleArea();
        System.out.println(area.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
    }

    public int largestRectangleArea(int[] heights) {
        int result = function_1(heights);
        return result;
    }

    private int function_1(int[] heights) {
        int max = 0;
        // 枚举所有高度
        // 遍历
        for (int i = 0; i < heights.length; i++) {
            // 拿到当前的高度
            int height = heights[i];
            // 定义宽度
            int width = 1;
            // 右边
            for (int j = i + 1; j < heights.length; j++) {
                // 拿到小于height的宽度
                if (heights[j] >= heights[i]) width++;
                else break;
            }
            // 左边
            for (int j = i - 1; j >= 0; j--) {
                if (heights[j] > heights[i]) width++;
                else break;
            }
            // 计算面积
            int area = width * height;
            if (max <= area) {
                max = area;
            }
        }
        return max;
    }
}
